package org.apache.commons.graph.algorithms.scc

import org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent
import org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseLabeledWeightedEdge
import org.apache.commons.graph.model.DirectedMutableGraph
import org.junit.Assert
import org.junit.Ignore
import org.junit.Test
import java.util.*

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Test for Tarjan's algorithm implementation,
 * see the [online](http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php) test.
 */
class TarjanTestCase {
    @Test
    fun testEmptyGraph() {
        val graph = DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>()

        findStronglyConnectedComponent(graph).applyingTarjan()
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>? = null
//        findStronglyConnectedComponent(graph).applyingTarjan()
//    }

    @Test
    fun testSparse() {
        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>> =
            newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>() {
                override fun connect() {
                    addVertex(BaseLabeledVertex("A"))
                    addVertex(BaseLabeledVertex("B"))
                    addVertex(BaseLabeledVertex("C"))
                    addVertex(BaseLabeledVertex("D"))
                    addVertex(BaseLabeledVertex("E"))
                    addVertex(BaseLabeledVertex("F"))
                }
            })

        // expected strong components
        val expected = 6

        // actual strong components
        val actual: Set<Set<BaseLabeledVertex>> = findStronglyConnectedComponent(graph).applyingTarjan()

        Assert.assertEquals(actual.size.toLong(), expected.toLong())
    }

    @Test
    @Ignore //TODO - for time being ignoring it.
    fun verifyHasStronglyConnectedComponents() {
        val a = BaseLabeledVertex("A")
        val b = BaseLabeledVertex("B")
        val c = BaseLabeledVertex("C")
        val d = BaseLabeledVertex("D")
        val e = BaseLabeledVertex("E")
        val f = BaseLabeledVertex("F")
        val g = BaseLabeledVertex("G")
        val h = BaseLabeledVertex("H")

        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newDirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    addVertex(a)
                    addVertex(b)
                    addVertex(c)
                    addVertex(d)
                    addVertex(e)
                    addVertex(f)
                    addVertex(g)
                    addVertex(h)

                    addEdge(BaseLabeledEdge("A -> F")).from(a).to(f)
                    addEdge(BaseLabeledEdge("A -> B")).from(a).to(b)
                    addEdge(BaseLabeledEdge("B -> D")).from(b).to(d)
                    addEdge(BaseLabeledEdge("C -> G")).from(c).to(g)
                    addEdge(BaseLabeledEdge("D -> A")).from(d).to(a)
                    addEdge(BaseLabeledEdge("D -> G")).from(d).to(g)
                    addEdge(BaseLabeledEdge("E -> C")).from(e).to(c)
                    addEdge(BaseLabeledEdge("E -> F")).from(e).to(f)
                    addEdge(BaseLabeledEdge("F -> E")).from(f).to(e)
                    addEdge(BaseLabeledEdge("G -> H")).from(g).to(h)
                    addEdge(BaseLabeledEdge("H -> C")).from(h).to(c)
                }
            })

        val expected: MutableSet<Set<BaseLabeledVertex>> = HashSet()
        val scc1 = mutableSetOf<BaseLabeledVertex>()
        Collections.addAll(scc1, a, b, d)
        expected.add(scc1)
        val scc2 = mutableSetOf<BaseLabeledVertex>()
        Collections.addAll(scc2, e, f)
        expected.add(scc2)
        val scc3 = mutableSetOf<BaseLabeledVertex>()
        Collections.addAll(scc3, g, h, c)
        expected.add(scc3)

        val actual: Set<Set<BaseLabeledVertex>> = findStronglyConnectedComponent(graph).applyingTarjan()

        Assert.assertFalse(actual.isEmpty())
        Assert.assertEquals(expected, actual)
    }
}
